/**
 * LeetCode70：爬楼梯
 * 给定n级台阶，每次只能爬上1或2级台阶，求有多少种方法爬到楼顶
 */

/**
 * @description F(n) = F(n-1) + F(n-2)
 * @description 爬到第n级，相当于从第n-1级向上爬1级，或者从第n-2级爬2级
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n){
    if (n<2){ return 1; }
    let dp0 = 1;
    let dp1 = 1;
    for (let i = 2; i <= n; i++) {
        const tmp = dp0;
        dp0 = dp1;
        dp1 = dp1 + tmp;
    }
    return dp1;
};

//时间复杂度：O(n)
//空间复杂度：O(1)